package wtx.geeks;

import static java.lang.Math.*;
import java.util.Random;
import java.util.StringJoiner;
/**
 * https://www.spoj.com/problems/GSS1/
 */
public final class QuerySubarrayMaxsum {
  public static long subarraySumMaxBrute(int[] array, int start, int end) {
    // case all negtive
    long max = Integer.MIN_VALUE;
    for (int i = start; i <= end; ++i) {
      if (array[i] > max) {
        max = array[i];
      }
    }
    if (max <= 0) {
      return max;
    }
    long sum = 0;
    for (int i = start; i <= end; ++i) {
      sum = 0;
      for (int j = i; j <= end; ++j) {
        sum += array[j];
        if (sum > max) {
          max = sum;
        }
      }
    }
    return max;
  }
  public static long subarraySumMax(int[] array, int start, int end) {
    // case all negtive
    long max = Integer.MIN_VALUE;
    for (int i = start; i <= end; ++i) {
      if (array[i] > max) {
        max = array[i];
      }
    }
    if (max <= 0) {
      return max;
    }
    long sum = 0;
    for (int i = start; i <= end; ++i) {
      sum += array[i];
      if (sum < 0) {
        sum = 0;
      }
      if (sum > max) {
        max = sum;
      }
    }
    return max;
  }

  
  private int[] T;
  private RangeInfo[] M;
  private int[] origArray;
  private static int MIN_VALUE = -20000;
  public void initTree(int[] array) {
    final int N = array.length;
    origArray = array;
    final int segLen = (int)Math.pow(2, ceil(log(N)/log(2)) + 1) - 1;
    T = new int [segLen];
    M = new RangeInfo[segLen];
    bT(0, 0, N);
    bM(0, 0, N);
  }
  private int bT(int idx, int left, int right) {
    if (right - left == 1) {
      T[idx] = origArray[left];
    } else {
      int mid = (left+right)/2;  
      int leftValue  = bT(idx*2 + 1, left,  mid);
      int rightValue = bT(idx*2 + 2, mid, right);
      T[idx] = leftValue + rightValue;
    }
    return T[idx];

  }
  private RangeInfo bM(int idx, int left, int right) {
    if (right - left > 1) {
      int mid = (left+right)/2;
      RangeInfo lv = bM(idx*2 + 1, left,  mid);
      RangeInfo rv = bM(idx*2 + 2, mid, right);
      if (lv.sv >= 0 && rv.sv >= 0) {
        int midV = fS(left, mid, lv.right, mid, 2*idx + 1) +
                       fS(mid, right, mid, rv.left, 2*idx + 2);
        // find internal max
        if (midV < 0) {
          int s = -1, e = -1, sm = 0, mx = 0;
          for (int i = lv.right; i < rv.left; ++i) {
            sm += origArray[i];
            if (sm < 0) {
              sm = 0;
            }
            if (sm > mx) {
              if (mx == 0) {
                s = i;
                e = i+1;
              } else {
                e = i+1;
              }
              mx = sm;
            }
          }
          if (s == lv.right) {
            lv = new RangeInfo(lv.left, e, lv.sv + mx);
          } else if (e == rv.left) {
            rv = new RangeInfo(s, rv.right, rv.sv + mx);
          }
          if (lv.sv == rv.sv) {
            return idx % 2 == 1 ? rv:lv;
          }
          return lv.sv > rv.sv ? lv : rv;

        } else {
          return new RangeInfo(lv.left, rv.right, lv.sv + rv.sv + midV);
        }
      } else {
        M[idx] = (lv.sv > rv.sv ? lv : rv);
      }
    } else {
      M[idx] = new RangeInfo(left, right, origArray[left]);
    }
    return M[idx];
  }
  private int fS(int ax, int ay, int left, int right, int h) {
    if (right - left <= 0) {
      return 0;
    }
    if (ay <= left || right < ax) {
      return 0;
    }
    if (ax + 1 == ay) {
      return T[h];
    }
    if (left == ax && right == ay) {
      return T[h];
    }
    int mid = (ax + ay) / 2;
    if (left < mid && mid < right) {
      int lv = fS(ax, mid, left, mid, 2*h+1);
      int rv = fS(mid, ay, mid, right, 2*h+2);
      return lv + rv;
    } else if (left < mid) {
      return fS(ax, mid, left, right, 2*h+1);
    } else {
      return fS(mid, ay, left, right, 2*h+2);
    }  
  }
  private static class RangeInfo {
    int left, right;
    int sv;
    RangeInfo(int l, int r, int v) {
      left = l;
      right = r;
      sv = v;
    }
    @Override
    public String toString() {
      return String.format("[%d, %d)= %d", left, right, sv);
    }
  }
  private static RangeInfo nullRange = new RangeInfo(0, 0, MIN_VALUE);
  public int subarraySumMaxSegTree(int left, int right) {
    RangeInfo r = _F(0, origArray.length, left, right, 0);
    return r.sv;
  }
  private RangeInfo _F(int ax, int ay, int left, int right, int h) {
    if (right - left <= 0) {
      return nullRange;
    }
    if (ay <= left || right < ax) {
      return nullRange;
    }
    if (ax + 1 == ay) {
      return M[h];
    }
    RangeInfo r = M[h];
    if (left <= r.left && right >= r.right) {
      int ret = 0, max = MIN_VALUE;
      for (int i = left; i < r.left; ++i) {
        ret -= origArray[i];
        if (ret < 0) {
          ret = 0;
        }
        if (ret > max) {
          max =
        }
      }
      ret += r.sv;

      for (int i = r.right; i < ay; ++i) {
        ret -= origArray[i];
      }
      return new RangeInfo(left, right, ret);
    }
    int mid = (ax + ay) / 2;
    if (left < mid && mid < right) {
      RangeInfo lv = _F(ax, mid, left, mid, 2*h+1);
      RangeInfo rv = _F(mid, ay, mid, right, 2*h+2);
      if (lv.sv >= 0 && rv.sv >= 0) {
        int mv = fS(ax, ay, lv.right, rv.left, 2*h + 1);
        if (mv < 0) {


        } else {
          return new RangeInfo(lv.left, rv.right, mv + lv.sv + rv.sv);
        }
      } else {
        return lv.sv > rv.sv ? lv : rv;
      }
    } else if (left < mid) {
      return _F(ax, mid, left, right, 2*h+1);
    } else {
      return _F(mid, ay, left, right, 2*h+2);
    }
  }
    /**
     * Says hello to the world.
     * @param args The arguments of the program.
     */
  public static void main(String[] args) {
    Random rnd = new Random(3263);

    for (int n = 0; n < 10; ++n) {
      final int arrayLen = rnd.nextInt(20) + 10;
      int[] array = new int[arrayLen];
      StringJoiner sj = new StringJoiner(",", "[", "]");
      for (int k = 0; k < arrayLen; ++k) {
        int c = rnd.nextInt(100) - 50;
        array[k] = c;
        sj.add("" + c);
      }
      System.out.println(String.format("array: %s", sj.toString()));
      QuerySubarrayMaxsum query = new QuerySubarrayMaxsum();
      query.initTree(array);
      for (int t = 0; t < 5; t++) {
        final int i = rnd.nextInt(arrayLen/2);
        int j = rnd.nextInt(arrayLen/2) + arrayLen/2;
        if (j >= arrayLen) {
          j = arrayLen - 1;
        }
        System.out.println(String.format("start = %d, end = %d\nmax sum = [%d, %d]", 
                i, j, subarraySumMaxBrute(array, i, j-1), query.subarraySumMaxSegTree(i, j)));
      }
    }
  }
}
